package com.veal98.bactrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC39 {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return res;
        }
        // 排序，防止出现重复组合
        Arrays.sort(candidates);
        List<Integer> track = new ArrayList<>();
        // 标志位，表示从数组的哪个位置开始选取
        int start = 0;
        backtrack(candidates, target, start, track);
        return res;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> track) {
        // 结束条件
        if (target == 0) {
            res.add(new ArrayList<>(track));
            return;
        }

        // 遍历选择列表
        for (int i = start; i < candidates.length; i ++) {
            // 剪枝
            if (candidates[i] > target) {
                // 因为数组已经排过序了，所以这里可以直接 break
                break;
            }
            // 做选择
            track.add(candidates[i]);
            target -= candidates[i];
            // 进入下一层解空间树
            backtrack(candidates, target, i, track);
            // 回溯
            track.remove(track.size() - 1);
            target += candidates[i];
        }
    }
}
